package com.lanluo.service.structure;

/**
 * 基于二叉查找树的符号表
 * @author
 * @date 2018-09-05-16:35
 */
public class BST<Key extends Comparable<Key>, Value> {
    private Node root;

    private class Node {
        private Key key;
        private Value val;
        private Node left, right;
        private int N;

        public Node(Key key, Value val, int n) {
            this.key = key;
            this.val = val;
            N = n;
        }
    }

    private int size(Node x) {
        if(x == null) return 0;
        else          return x.N;
    }

    public int size() {
        return size(root);
    }

    public void put(Key key, Value val) {
        root = put(root, key, val);
    }

    private Node put(Node x, Key key, Value val) {
        if(x == null) return new Node(key, val, 1);
        int cmp = key.compareTo(x.key);
        if  (cmp < 0)       x.left = put(x.left, key, val);
        else if(cmp > 0)    x.right = put(x.right, key, val);
        else                x.val = val;
        x.N = size(x.left) + size(x.right) + 1;
        return x;
    }

    public Value get(Key key) {
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        if(x == null) return null;
        int cmp = key.compareTo(x.key);
        if(cmp < 0) return get(x.left, key);
        else if (cmp > 0) return get(x.right, key);
        else return x.val;
    }

    public static void main(String[] args) {
        BST<String, String> bst = new BST<String, String>();
        bst.put("b", "的");
        bst.put("a", "我");
        bst.put("c", "世");
        bst.put("e", "啊");
        bst.put("d", "界");
        System.out.println(bst.get("e"));
    }

}